#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    //@ ysh's method
    // void traceback(string &s, int start_index)
    // {
    //     if (path.size() > 4)
    //     {
    //         return;
    //     }
    //     if (path.size() == 4 && start_index >= (int)s.size())
    //     {
    //         string s;
    //         for (auto num : path)
    //         {
    //             s += to_string(num);
    //             s += ".";
    //         }
    //         s.pop_back();
    //         res.push_back(s);
    //         return;
    //     }
    //     for (int i = start_index; i < (int)s.size(); i++)
    //     {
    //         string str = s.substr(start_index, i - start_index + 1);
    //         if (str.size() > 1 && str[0] == '0')
    //         {
    //             break;
    //         }
    //         int num = stoi(str);
    //         if (num > 255)
    //         {
    //             break;
    //         }
    //         path.push_back(num);
    //         traceback(s, i + 1);
    //         path.pop_back();
    //     }
    // }
    // vector<string> restoreIpAddresses(string s)
    // {
    //     res.clear();
    //     path.clear();
    //     traceback(s, 0);
    //     return res;
    // }
    // vector<string> res;
    // vector<int> path;

    //@ book answer
    bool is_valid(string &s, int start, int end)
    {
        if (start > end)
        {
            return false;
        }
        else if (s[start] == '0' && start != end)
        {
            return false;
        }
        else
        {
            int num = 0;
            for (int i = start; i <= end; i++)
            {
                if (s[i] <= '0' && s[i] >= '9')
                {
                    return false;
                }
                num = num * 10;
                num += (s[i] - '0');
                if (num > 255)
                {
                    return false;
                }
            }
        }
        return true;
    }
    void traceback(string &s, int start_index, int point_num)
    {
        if (point_num == 3)
        {
            if (is_valid(s, start_index, s.size() - 1))
            {
                res.push_back(s);
            }
            return;
        }
        for (int i = start_index; i < (int)s.size(); i++)
        {
            if (is_valid(s, start_index, i))
            {
                s.insert(s.begin() + i + 1, '.');
                point_num++;
                traceback(s, i + 2, point_num);
                point_num--;
                s.erase(s.begin() + i + 1);
            }
            else
            {
                break;
            }
        }
    }
    vector<string> restoreIpAddresses(string s)
    {
        res.clear();
        if (s.size() < 4 || s.size() > 12)
        {
            return res;
        }
        traceback(s, 0, 0);
        return res;
    }  
    vector<string> res;
};

int main()
{
    Solution sol;
    vector<string> res = sol.restoreIpAddresses("2222");
    for (auto s : res)
    {
        cout << s << endl;
    }
    return 0;
}